import java.util.Random;

public class LeetCode {
    public int[] sortArray(int[] nums) {
        qsort(nums,0,nums.length - 1);
        return nums;
    }
    public void qsort(int[] nums,int l,int r){
        if(l>=r){
            return;
        }
        //数组分三块
        int k = nums[new Random().nextInt(r-l+1)+l];
        int left = l-1,right = r+1,i = l;
        while(i < right){
            if(nums[i] < k){
                swap(nums,++left,i++);
            }else if(nums[i] == k){
                i++;
            }else{
                swap(nums,--right,i);
            }
        }
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
    public void swap(int nums[],int l,int r){
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
    public int findKthLargest(int[] nums, int k) {
        return qqsort(nums,0,nums.length-1,k);
    }
    public int qqsort(int nums[],int l,int r,int k){
        if(l == r){
            return nums[l];
        }
        //1.随机选择一个基准元素
        int key = nums[new Random().nextInt(r-l+1)+l];
        //2.根据基准元素使素组分三块
        int right = r+1,left = l-1,i = l;
        while(i<right){
            if(nums[i] < key){
                swap(nums,++left,i++);
            }else if(nums[i] == key){
                i++;
            }else{
                swap(nums,i,--right);
            }
        }
        //3.分类讨论
        //[l,left] [left+1,right-1] [right , r]
        int b = right - left - 1,c = r-right+1;
        if(c>=k){
            return qqsort(nums,right,r,k);
        }else if(c+b>=k){
            return key;
        }else{
            return qqsort(nums,l,left,k-b-c);
        }
    }
    public int[] getLeastNumbers(int[] arr,int k){
       sort(arr,0,arr.length - 1,k);
       int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = arr[i];
        }
        return  ret;
    }
    public void sort(int[] arr,int l,int r,int k){
        if(l == r){
            return;
        }

        int key = arr[new Random().nextInt(r-l+1)+l];
        int left = l-1,right = r+1,i = l;
        while(i < right){
            if(arr[i] < key){
                swap(arr,++left,i++);
            }else if(arr[i] == key){
                i++;
            }else{
                swap(arr,--right,i);
            }
        }
        //[l,left] [left+1,right-1] [right , r]
        int a = left - l+1;
        int b = right - left - 1;
        if(a>k){
            sort(arr,l,left,k);
        }else if(a+b>=k){
            return;
        }else{
            sort(arr,right,r,k-a-b);
        }

    }
}
